On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).
Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.
You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?
Example 1:
Input: [[0,2],[1,3]] Output: 3 Explanation: At time0, you are in grid location(0, 0). You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0. You cannot reach point(1, 1)until time3. When the depth of water is3, we can swim anywhere inside the grid.
Example 2:
Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] Output: 16 Explanation: 0 1 2 3 4 24 23 22 21 5 12 13 14 15 16 11 17 18 19 20 10 9 8 7 6 The final route is marked in bold. We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
Note:
2 <= N <= 50.- grid[i][j] is a permutation of [0, ..., N*N - 1].
Average Rating: 4.45 (22 votes)
Approach #1: Heap [Accepted]
Intuition and Algorithm
Let's keep a priority queue of which square we can walk in next. We always walk in the smallest one that is 4-directionally adjacent to ones we've visited.
When we reach the target, the largest number we've visited so far is the answer.
Complexity Analysis
-
Time Complexity: O(N2logN). We may expand O(N2) nodes, and each one requires O(logN) time to perform the heap operations.
-
Space Complexity: O(N2), the maximum size of the heap.
Approach #2: Binary Search and DFS [Accepted]
Intuition and Algorithm
Whether the swim is possible is a monotone function with respect to time, so we can binary search this function for the correct time: the smallest T for which the swim is possible.
Say we guess that the correct time is T. To check whether it is possible, we perform a simple depth-first search where we can only walk in squares that are at most T.
Complexity Analysis
-
Time Complexity: O(N2logN). Our depth-first search during a call to
possibleis O(N2), and we make up to O(logN) of them. -
Space Complexity: O(N2), the maximum size of the stack.
Approach #3: Minimal Spanning Tree Algorithm (Union-Find)
Intuition
One can formulate the problem as building a minimum spanning tree, i.e. find minimum edges to connect all nodes in a graph.
In our case, we would like to find the fastest path (i.e. minimal waiting time) to reach from the top-left point to the bottom-right point of the grid.
Rather than finding the spanning tree to connect all cells in the grid, we are only interested to find the spanning that connect our starting and ending points.
One of the well-known algorithms for the minimal spanning tree problem is called Kruskal's algorithm, proposed by Joseph Kruskal in 1956.
So the idea of this solution is to adapt the Kruskal's algorithm to solve our problem here.
Algorithm
The essence of the Kruskal's algorithm relies on the disjoint-set data structure, also known as union-find data structure, which tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
The Kruskal's algorithm starts from a list of sets, where each set contains only a single node, it then greedily merges the sets together until there is only one set left i.e. the minimal spanning tree.
Essentially, the algorithm can be implemented with two major functions: union(a, b) and find(a).
With the union(a, b) function, we merge two sets together. And with the find(a) function, we find the representative (also known as parent) of the set.
Here are some overall steps of an adapted Kruskal's algorithm:
-
We consider each cell in the grid as a node in a graph, and the value in the cell represents its weight.
-
We then sort the cells based on their weights, in the ascending order.
-
We then iterate through the sorted cells.
-
At each iteration, we add the neighbor cells around the current cell to the spanning tree.
-
At any moment, if we find that the starting and ending points are connected thanks to the newly added nodes, we exit the loop. And the weight of the current cell would be the minimal waiting time, before we complete the spanning tree.
-
Here is the solution proposed by leet212. Also, many users have proposed similar ideas and solutions in the discussion forum.
Complexity Analysis
Let N be the width of the grid (N*N).
-
Time Complexity: O(N2logN2).
-
First of all, we have in total N2 cells in the grid.
-
Since we sort cells based on their weights, it would take O(N2logN2) time for this sorting operation.
-
We iterate through the cells, i.e. N2 steps. At each step, the
union()function requires O(log∗N2) complexity, which one can refer to the proof for more details. -
To sum up, the overall time complexity of the algorithm is O(N2logN2)+O(N2log∗N2)=O(N2logN2).
-
-
Space Complexity: O(N2). We use some auxiliary data structures that are proportional to the size of the grid, i.e. N2.
Last Edit: July 21, 2019 5:10 AM
Share my O(n^2) union find solution that only use union find, no heap, dfs, dp or binary search
class Solution {
private static final int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int[] parents;
private int[] ranks;
private void buildUnionFind(int rows, int cols) {
parents = new int[rows * cols];
ranks = new int[rows * cols];
for (int i = 0; i < parents.length; ++i) {
parents[i] = i;
ranks[i] = 1;
}
}
private int find(int id) {
while (id != parents[id]) {
parents[id] = parents[parents[id]];
id = parents[id];
}
return id;
}
private boolean connected(int p, int q) {
return find(p) == find(q);
}
private void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (ranks[rootP] <= ranks[rootQ]) {
parents[rootP] = rootQ;
ranks[rootQ] += ranks[rootP];
} else {
parents[rootQ] = rootP;
ranks[rootP] += ranks[rootQ];
}
}
public int swimInWater(int[][] grid) {
int N = grid.length;
buildUnionFind(N, N);
int[] map = new int[N * N];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
map[grid[i][j]] = i * N + j;
}
}
for (int time = 0; time < N * N; ++time) {
int idx = map[time];
int row = idx / N;
int col = idx % N;
for (int[] direction : directions) {
int rr = row + direction[0], cc = col + direction[1];
if (!isValid(rr, cc, grid, time)) continue;
union(idx, rr * N + cc);
}
if (connected(0, N * N - 1)) return time;
}
return -1;
}
private boolean isValid(int r, int c, int[][] grid, int time) {
return r >= 0 && r < grid.length && c >= 0 && c < grid.length && grid[r][c] < time;
}
}
February 22, 2019 11:53 AM
What does it mean "At time t, the depth of the water everywhere is t"? Everywhere or the cell with lower elevation? It is confusing....
Another way to solve this problem (more efficiently) is to use Disjoint Set data structure (like in Kruskal's algorithm for finding minimum spanning tree). This way you can reduce time complexity down to O(N^2). We go from 0 to N^2 and choose a Point on the grid with that value. Then we merge it with all its neighbours whose value is less than this Point's value.
Is there a proof that the first solution, indeed, finds an optimal solution? It operates in a greedy manner but greedy algos are, in general, not guaranteed to reach the optimal solution.
November 24, 2019 3:15 PM
Can somebody explain the question, i don't get it at all?
Another solution is Weighted Union Find algorithm: https://www.coursera.org/learn/algorithms-part1/lecture/fjxHC/dynamic-connectivity
hm.. ok so the binary search solution is based on that we know that lower and upper limit of grid[I][j]. If we don't know && if grid[I][j] is strongly biased, meaning that some 1 s and some 1000000000000 s, binary search probably won't work that well?
Where is parameter "T" being used in binary search solution in possible function?
Why hi is initialised to N2 isn't it should be max( grid[I][j])
June 7, 2018 9:33 PM
Another solution would be to use Dijstrka. We can use as distance the max. of the current distance and the height of the neighbour. The running time is also O(N^2 log N)
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int swimInWater(vector<vector<int>>& grid) { }};